/**
 * 154. 寻找旋转排序数组中的最小值 II【困难】（与 153，剑指 Offer 11 同）
 * https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
 */
public class Solutions_154 {
    public static void main(String[] args) {
//        int[] nums = {1, 3, 5};  // output: 1
//        int[] nums = {2, 2, 2, 0, 1};  // output: 0
        int[] nums = {3, 1};  // output: 1

        int result = findMin2(nums);
        System.out.println(result);
    }

    /**
     * 二分查找法
     * 在数组有序的情况，可以采用二分查找来提高程序效率
     * 计算好二分中间索引后，有三种情况
     * 1. nums[mid] == nums[right]，有重复元素，right 减 1 来去除重复元素
     * 2. nums[mid] < nums[right]，mid 右侧的都是较大元素，不可能存在最小元素了
     * 3. nums[mid] > nums[right]，mid 右侧的元素包含了翻转后的元素，
     *                              即最小元素一定在 mid 右侧的部分
     */
    public static int findMin(int[] nums) {
        if (nums == null || nums.length < 1) {
            return - 1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == nums[right]) {
                // 去除重复元素
                right --;
            } else if (nums[mid] > nums[right]) {
                // 最小元素在 mid 后面，查找区间排除 mid 及 mid 前面的部分
                left = mid + 1;
            } else {
                // 最小元素可能为 mid，或者在 mid 前面，查找区间排除 mid 后面的部分
                right = mid;
            }
        }
        return nums[left];
    }

    /**
     * 线性查找法，效率较差
     * [0, len - 1] 中的每个元素，与其后一个元素比较，大于后一个元素时，后一个元素一定是最小元素
     */
    public static int findMin2(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                // 找到翻转后的起点，即最小的元素
                return nums[i + 1];
            }
        }
        return nums[0];
    }
}
